package binaryTree.review;

import binaryTree.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

public class Iteration1 {

    //前序　根左右　加入顺序　　右左根
    public List<Integer> preOrderTraverse(TreeNode root) {
        if (root == null) {
            return null;
        }
        Stack<TreeNode> st = new Stack<>();
        st.push(root);
        ArrayList<Integer> list = new ArrayList<>();
        while (!st.isEmpty()) {
            TreeNode node = st.peek();
            if (node != null) {
                st.pop();
                if (node.right != null) {
                    st.push(node.right);
                }
                if (node.left != null) {
                    st.push(node.left);
                }
                st.push(node);
                st.push(null);
            } else {
                st.pop();
                node = st.peek();
                st.pop();
                list.add(node.val);
            }
        }
        return list;
    }



    //中序　左根右　加入顺序　　右根左
    public List<Integer> inOrderTraverse(TreeNode root) {
        if (root == null) {
            return null;
        }
        Stack<TreeNode> st = new Stack<>();
        st.push(root);
        ArrayList<Integer> list = new ArrayList<>();
        while (!st.isEmpty()) {
            TreeNode node = st.peek();
            if (node != null) {
                st.pop();
                if (node.right != null) {
                    st.push(node.right);
                }
                st.push(node);
                st.push(null);

                if (node.left != null) {
                    st.push(node.left);
                }

            } else {
                st.pop();
                node = st.peek();
                st.pop();
                list.add(node.val);
            }
        }
        return list;
    }
    //后序　左右根　加入顺序　　根右左
    public List<Integer> postOrderTraverse(TreeNode root) {
        if (root == null) {
            return null;
        }
        Stack<TreeNode> st = new Stack<>();
        st.push(root);
        ArrayList<Integer> list = new ArrayList<>();
        while (!st.isEmpty()) {
            TreeNode node = st.peek();
            if (node != null) {
                st.pop();
                st.push(node);
                st.push(null);
                if (node.right != null) {
                    st.push(node.right);
                }
                if (node.left != null) {
                    st.push(node.left);
                }

            } else {
                st.pop();
                node = st.peek();
                st.pop();
                list.add(node.val);
            }
        }
        return list;
    }

    public static void main(String[] args) {

        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode4 = new TreeNode(4);
        treeNode1.left=treeNode3;
        treeNode3.left=treeNode2;
        treeNode3.right=treeNode4;

        Iteration1 iteration1 = new Iteration1();
        List<Integer> list1 = iteration1.preOrderTraverse(treeNode1);
        for (int a: list1
             ) {
            System.out.println(a);

        }
        System.out.println("===========================");
        List<Integer> list2 = iteration1.inOrderTraverse(treeNode1);
        for (int a: list2
        ) {
            System.out.println(a);

        }
        System.out.println("===========================");

        List<Integer> list3 = iteration1.postOrderTraverse(treeNode1);
        for (int a: list3
        ) {
            System.out.println(a);

        }
        System.out.println("===========================");


    }


}
